#include <iostream>
#include <vector>
#include <algorithm>

// 向下调整建大堆
void adjustDown(std::vector<int> &nums, int n, int parent)
{
    int maxchild = parent * 2 + 1;
    while (maxchild < n)
    {
        if (maxchild + 1 < n && nums[maxchild] < nums[maxchild + 1])
        {
            maxchild++;
        }

        if (nums[parent] < nums[maxchild])
        {
            std::swap(nums[parent], nums[maxchild]);
            parent = maxchild;
            maxchild = parent * 2 + 1;
        }
        else
            break;
    }
}

void heap_sort(std::vector<int> &nums)
{
    int n = nums.size();

    // 向下调整建堆 O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        adjustDown(nums, n, i);
    }

    // O(N*logN)
    int i = 1;
    while (i < n)
    {
        std::swap(nums[0], nums[n - i]);
        adjustDown(nums, n - i, 0);
        i++;
    }
}

int main()
{
    std::vector<int> nums = {10, 2, 3, 5, 4, 8, 7, 6, 8, 9, 1};
    heap_sort(nums);
    for (auto x : nums)
    {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}